package leetcode.pre100;

import java.util.Arrays;

/**
 * 给你两个有序整数数组 nums1 和 nums2，请你将 nums2 合并到 nums1 中，使 nums1 成为一个有序数组。
 * <p>
 *  
 * <p>
 * 说明:
 * <p>
 * 初始化 nums1 和 nums2 的元素数量分别为 m 和 n 。
 * 你可以假设 nums1 有足够的空间（空间大小大于或等于 m + n）来保存 nums2 中的元素。
 *  
 * <p>
 * 示例:
 * <p>
 * 输入:
 * nums1 = [1,2,3,0,0,0], m = 3
 * nums2 = [2,5,6],       n = 3
 * <p>
 * 输出: [1,2,2,3,5,6]
 *
 * @date 2020/6/8 17:49
 */
public class Code88_MergeTwoSortedNums {
    /**
     * 方式1：直接复制，然后排序
     */
    public void merge1(int[] nums1, int m, int[] nums2, int n) {
        /**
         * origin nums, startIndex
         * target nums, startIndex ,len--copy length
         */
        System.arraycopy(nums2, 0, nums1, m, n);
        Arrays.sort(nums1);
    }

    /**
     * 方式2：利用额外空间外排
     * 注意由于最后要拷贝到nums1中，所以利用nums和nums2进行外排
     */
    public void merge2(int[] nums1, int m, int[] nums2, int n) {
        int[] nums = Arrays.copyOf(nums1, m);
        int i = 0;
        int j = 0;
        int p = 0;
        while (i < m && j < n) {
            nums1[p++] = (nums[i] <= nums2[j] ? nums[i++] : nums2[j++]);
        }
        //排列了 i+j个  一个是 0-i-1,另一个是0-j-1，总共 i+j个
        if (i < m)
            System.arraycopy(nums, i, nums1, i + j, m + n - i - j);
        if (j < n)
            System.arraycopy(nums2, j, nums1, i + j, m + n - i - j);

    }

    /**
     * 方式3：还是外排。
     * 在原来两个数组中，如果从头开始外排，并且没有额外辅助空间，
     * 那么nums1中大的数可能会被nums2中小的数覆盖掉
     * <p>
     * 解决方法：
     * 从两个数组的最后元素进行外排，这样就不会覆盖.
     * 因为总共有m+n个空间，然后有m+n个元素 ，每个元素要占用一个空间，不会被覆盖的
     */
    public void merge3(int[] nums1, int m, int[] nums2, int n) {
        int[] nums = Arrays.copyOf(nums1, m);
        int i = m - 1;
        int j = n - 1;
        int p = m + n - 1;
        while (i >= 0 && j >= 0) {
            nums1[p--] = (nums1[i] >= nums2[j] ? nums1[i--] : nums2[j--]);
        }
        //数组2从 0 - j 要拷贝到数组1中
        if(i < 0){
            System.arraycopy(nums2, 0, nums1, 0, j+1);
        }
        //数组1从 0-i要拷贝到数组1中，不用动，本来就在
        if(j < 0);//doNothing
    }
}
